# 暴力
class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        n, m = len(spells), len(potions)
        pairs = [0] * n
        for i in range(n):
            temp = 0
            for j in range(m):
                if spells[i] * potions[j] >= success:
                    temp += 1
            pairs[i] = temp
        
        return pairs
#二分查找
class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        n, m = len(spells), len(potions)
        potions.sort() # 递增排序
        pairs = [0] * n
        for i in range(n):
            left, right = 0, m - 1
            while left <= right: # 二分查找
                mid = (left + right) // 2
                if spells[i] * potions[mid] >= success:
                    right = mid - 1
                else:
                    left = mid + 1
            pairs[i] = m - left 
        
        return pairs